package com.coder.algorithm.leetcode

import com.coder.algorithm.struct.ListNode

/**
 * [19. 删除链表的倒数第 N 个结点](https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/)
 *
 * @author yuhus
 * @date: 2022/4/1
 */
object l_0019 {
    /**
     * 链表中结点的数目为 `sz`
     * 1 <= sz <= 30
     * 1 <= n <= sz
     *
     */
    fun removeNthFromEnd(head: ListNode?, n: Int): ListNode? {
        val preHead = ListNode(0)
        preHead.next = head
        var fast: ListNode? = preHead
        var slow: ListNode? = preHead
        for (i in 1..n) {
            fast = fast?.next
        }
        while (fast?.next != null) {
            fast = fast?.next
            slow = slow?.next
        }
        var prev = slow
        prev?.next = prev?.next?.next
        return preHead.next
    }
}